The invention relates to converting digital computer graphics involving the processing of raster and vector data.
In computer graphics, two basic forms of representation are used to definer an image: raster and vector. In a raster representation, a bitmap specifies a set of pixel values at a set of raster positions to define an image. In this document, the term bitmap will include structures that have a bit depth greater than one in which pixels are defined by more than one bit of data; however, the bitmap will always be treated as binary, that is, each pixel position will be treated as being either on or off, image (foreground) or background. A bitmap generally has a rectangular structure. In a vector representation, resolution-independent vectors and their properties (such as fill pattern and color) define an image.
It is sometimes convenient or necessary to obtain a vector representation of one or more regions in a bitmap, for example to manipulate the shape of a bitmap region, to scale a bitmap region, to trap an object, or to clip a vector object against a bitmap mask. One method for obtaining a vector representation is to trace around the boundary of the bitmap object from pixel to pixel to create a closed contour, or polygon, corresponding to the bitmap object. However, such methods typically use the centers of traced pixels to generate the vertices of the polygon enclosed the region, and therefore can introduce as much as a half-pixel error in the conversion to a polygon. In many applications, this is an acceptable error. However, if a purpose of conversion is to use the polygon to clip another vector object, for example, and the polygon must be mapped to a new coordinate system, the half-pixel error can become several pixels in the new coordinate system. This several-pixel error may not be acceptable.